package edu.android.com;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import android.app.Activity;
import android.graphics.Color;
import android.os.Bundle;
import android.os.Handler;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.FrameLayout;
import android.widget.Toast;

public class dirFlow extends framework{
	
	private int START,END;
	private int[][] C,F;
	private int[] father;
	private int Flow;
	private ArrayList <edge>[] graph;
	
	@Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        
        //Visibility ...
        EditText mStartNode = (EditText)findViewById(R.id.startNode);
        mStartNode.setVisibility(EditText.INVISIBLE);
        
        //Start This
        Button mPickStartNode = (Button)findViewById(R.id.pickStartNode);
        
        mPickStartNode.setOnClickListener(new View.OnClickListener() {
			@Override
			public void onClick(View v) {
				// TODO Auto-generated method stub
				startThis();
			}
		});
        
        Toast.makeText(getApplicationContext(), "Source Node : 1 |  Destination Node : n", Toast.LENGTH_SHORT).show();
        Toast.makeText(getApplicationContext(), "Don't add two edges between same nodes!!!", Toast.LENGTH_SHORT).show();
        
        setEdgePrefereces();
    }
	
	private void setEdgePrefereces(){
		edge.mOrientated = true;
		edge.mWithCost = false;
		edge.mWithFlow = true;
	}
	
	private void setDefault(){
		int len = mNodes.size();
		START = 1;	END = len;	Flow = 0;
		C = new int [len + 1][len + 1];
		F = new int [len + 1][len + 1];
		father = new int[len + 1];
		used = new boolean[len + 1];
		
		graph = (ArrayList<edge>[]) new ArrayList[len + 1];
		
		for(int i = 1;i <= len;i ++){
			used[i] = false;
			father[i] = 0;
			graph[i] = new ArrayList <edge>();
		}
		for(int i = 1;i <= len;i ++)
			for(int j = 1;j <= len;j ++){
				C[i][j] = F[i][j] = 0;
			}
		
		for(int i = 0;i < len;i ++){
			mNodes.get(i).initialize();
		}
	}
	
	private void startThis(){
		setDefault();
		
		for(int i = 0;i < mNodes.size();i ++){
			node nd = mNodes.get(i);
			for(int j = 0;j < nd.mEdges.size();j ++){
				//Set Capacity
				C[nd.getNodeNumber()][nd.mEdges.get(j).secondNode.getNodeNumber()] = nd.mEdges.get(j).getCapacity();
				//Create the graph;
				graph[nd.getNodeNumber()].add(nd.mEdges.get(j));
				graph[nd.mEdges.get(j).secondNode.getNodeNumber()].add(nd.mEdges.get(j));
			}
		}
		
		while(BF())
		{
			int Min = (1<<30);
			for(int nd = END;nd != START;nd = father[nd])
				Min = Math.min(Min,C[father[nd]][nd]-F[father[nd]][nd]);
			if(Min == 0)
				continue;
			for(int nd = END;nd != START;nd = father[nd])
			{
				F[father[nd]][nd] += Min;
				F[nd][father[nd]] -= Min;
			}
			Flow += Min;
		}
		
		for(int i = 0;i < mNodes.size();i ++){
			node nd = mNodes.get(i);
			for(int j = 0;j < nd.mEdges.size();j ++){
				node next = nd.mEdges.get(j).secondNode;
				int flow = F[nd.getNodeNumber()][next.getNodeNumber()];
				if(flow >= 0)
					nd.mEdges.get(j).setFlow(flow);
			}
		}
		showToScreen();
	}
	private boolean BF(){
		for(int i = 1;i <= mmNrNodes;i ++)
			used[i] = false;
		
		Queue <Integer> mQ = new LinkedList();
		mQ.add(START);
		used[START] = true;
		
		while(!mQ.isEmpty()){
			int nd = mQ.poll();
			if(nd == END)
				continue;
			int next = 0;
			for(int i = 0;i < graph[nd].size();i ++){
				node left = graph[nd].get(i).firstNode;
				node right = graph[nd].get(i).secondNode;
				
				if(left.getNodeNumber() != nd)
					next = left.getNodeNumber();
				else
					if(right.getNodeNumber() != nd)
						next = right.getNodeNumber();
				if(C[nd][next] <= F[nd][next] || used[next])
					continue;
				used[next] = true;
				father[next] = nd;
				mQ.add(next);
			}
		}
		return used[END];
	}

	private void showToScreen(){
		showOrder();
	}
	private void showOrder(){
		String toast = "Maximum Flow : " + Flow;
		mDisplayContent.setText(toast);
	}
}
